#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    /// 1143. 最长公共子序列
    // https://leetcode.cn/problems/longest-common-subsequence/
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1));
        text1 = ' ' + text1;
        text2 = ' ' + text2;

        for (int i = 1; i<=n1; ++i)
        {
            for (int j = 1; j<=n2; ++j)
            {
                if (text1[i] == text2[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
        }

        return dp[n1][n2];
    }

    // 1035. 不相交的线
    // https://leetcode.cn/problems/uncrossed-lines/
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1));

        for (int i = 1; i<=n1; ++i)
        {
            for (int j = 1; j<=n2; ++j)
            {
                if (nums1[i-1] == nums2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
        }

        return dp[n1][n2];
    }
};